'''
https://leetcode.cn/problems/shortest-path-in-binary-matrix/?envType=study-plan-v2&envId=graph-theory
'''
from collections import deque
from typing import List


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] == 1 or grid[-1][-1] == 1: return -1
        m, n = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]
        q = deque([(0, 0)])
        visited = [[False] * n for _ in range(m)]
        step = 1
        while q:
            for _ in range(len(q)):
                x, y = q.popleft()
                if x == m - 1 and y == n - 1:
                    return step
                if visited[x][y]:
                    continue
                visited[x][y] = True
                for tx, ty in directions:
                    tx, ty = x + tx, y + ty
                    if 0 <= tx < m and 0 <= ty < n and grid[tx][ty] == 0:
                        q.append((tx, ty))
            step += 1
        return -1